package Graph.graphWithNoweight.dfs;


import java.util.ArrayList;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/6 20:17
 * @Version 1.0
 *
 * 环检测核心思想：一个节点被重复遍历了，并且
 */
public class CycleDetection {

    private Graph G;
    private boolean[] visited;
    private boolean hasCycle;

    private ArrayList<Integer> order = new ArrayList<>();

    public CycleDetection(Graph G){
        this.G = G;
        visited = new boolean[G.V()];
        for(int v=0;v<G.V();v++){
            if(!visited[v]){
                if(dfs(v,v)){
                    hasCycle = true;
                    //这里就先不break了。因为 break 如果有其他环就不会遍历到，也无法从visited里面看出来。
                };
            }
        }
    }

    //从顶点v 开始判断图中是否有环
    //返回值：true 代表有环，，false 代表无环。
    private boolean dfs(int v,int parent) {
        visited[v] = true;
        order.add(v);
        for(int w:G.adj(v)){
            if(!visited[w]){
                if(dfs(w,v)){
                    return true;
                };
            }else if(w!=parent){
                //进入else if 了说明这个节点已经被访问过了，如果这个时候，w！=parent 就能说明，是一个环
                //hasCycle = true;
                return true;
            }
        }
        return false;
    }

    public Iterable<Integer> order(){
        return order;
    }

    public boolean hasCycle(){
        return this.hasCycle;
    }

    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        CycleDetection graphDFS = new CycleDetection(g);
        System.out.println(graphDFS.hasCycle());
    }
}
